The purpose of this research study is to evaluate a new experimental treatment using a vaccine to treat cancer. The vaccine is a canarypox virus (ALVAC) that co-expresses the human carcinoembryonic antigen (CEA) and the so-stimulatory molecule B7-1. This is expected to activate T-cell responses against CEA-expressing tumor cells. This protocol is a phase I trial designed to determine the optimal dose of vaccine, side effects, clinical and immune responses. Increasing doses of virus will be used in patients with advanced CEA-expressing tumors by monthly intramuscular injections over 3 months. This study proposes to treat six patients at each dose of virus and will analyze immune responses after each immunization by in vitro T-cell assays and clinical responses after the 3 month treatment period. Patients without progression may be re-vaccinated.